package leetcode;

import java.util.List;

/**
 * 148.排序链表
 * 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 4->2->1->3
 * 输出: 1->2->3->4
 * 示例 2:
 * <p>
 * 输入: -1->5->3->4->0
 * 输出: -1->0->3->4->5
 * <p>
 */
public class SortList1 {

    public static void main(String[] args) {
        ListNode node = new ListNode(23);
        new SortList1().sortList(node);
    }

    /**
     * 使用归并算法，类似数组的归并算法，n*log(n)
     *
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
        // 判断递归是否结束
        if (head == null || head.next == null) {
            return head;
        }

        ListNode mid = middleNode(head);
        ListNode right = mid.next;
        mid.next = null;

        ListNode left = sortList(head);
        ListNode right1 = sortList(right);

        return merge(left, right1);

    }


    // 找到链表中点节点
    ListNode middleNode(ListNode node) {
        ListNode cur = node;
        int length = 0;
        while (cur != null) {
            length++;
            cur = cur.next;
        }

        if (length <= 2) {
            return node;
        }


        ListNode mid = node;
        int leftLength = length % 2 == 1 ? length / 2 +1 : length / 2;
        while (leftLength > 1) {
            mid = mid.next;
            leftLength--;
        }
        return mid;
    }

    // 找到链表中点节点
    ListNode middleNode1(ListNode node) {

        if (node == null || node.next == null) {
            return node;
        }
        ListNode slow = node;
        ListNode fast = node.next.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    ListNode merge(ListNode left, ListNode right) {
        ListNode node = new ListNode(0);
        ListNode head = node;
        while (left != null && right != null) {
            if (left.val < right.val) {
                node.next = left;
                left = left.next;
            } else {
                node.next = right;
                right = right.next;
            }
            node = node.next;
        }
        node.next = left != null ? left : right;
        return head.next;
    }


    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}


